<!DOCTYPE HTML>
<html lang="zh-CN" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title> Section 3.4 - PurpleDragonBookAnswer</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="Purple Dragon Book Answer Online Edition">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../../favicon.svg">
        <link rel="shortcut icon" href="../../favicon.png">
        <link rel="stylesheet" href="../../css/variables.css">
        <link rel="stylesheet" href="../../css/general.css">
        <link rel="stylesheet" href="../../css/chrome.css">
        <link rel="stylesheet" href="../../css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../../fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../../highlight.css">
        <link rel="stylesheet" href="../../tomorrow-night.css">
        <link rel="stylesheet" href="../../ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "../../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded "><a href="../../preface.html"><strong aria-hidden="true">1.</strong> Preface</a></li><li class="chapter-item expanded "><a href="../../ch01/ch01.html"><strong aria-hidden="true">2.</strong> Chapter 1</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch01/1.1/1.1.html"><strong aria-hidden="true">2.1.</strong> Section 1.1</a></li><li class="chapter-item expanded "><a href="../../ch01/1.3/1.3.html"><strong aria-hidden="true">2.2.</strong> Section 1.3</a></li><li class="chapter-item expanded "><a href="../../ch01/1.6/1.6.html"><strong aria-hidden="true">2.3.</strong> Section 1.6</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch02/ch02.html"><strong aria-hidden="true">3.</strong> Chapter 2</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch02/key-point/key-point.html"><strong aria-hidden="true">3.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch02/2.2/2.2.html"><strong aria-hidden="true">3.2.</strong> Section 2.2</a></li><li class="chapter-item expanded "><a href="../../ch02/2.3/2.3.html"><strong aria-hidden="true">3.3.</strong> Section 2.3</a></li><li class="chapter-item expanded "><a href="../../ch02/2.4/2.4.html"><strong aria-hidden="true">3.4.</strong> Section 2.4</a></li><li class="chapter-item expanded "><a href="../../ch02/2.6/2.6.html"><strong aria-hidden="true">3.5.</strong> Section 2.6</a></li><li class="chapter-item expanded "><a href="../../ch02/2.8/2.8.html"><strong aria-hidden="true">3.6.</strong> Section 2.8</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch03/ch03.html"><strong aria-hidden="true">4.</strong> Chapter 3</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch03/key-point/key-point.html"><strong aria-hidden="true">4.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch03/3.1/3.1.html"><strong aria-hidden="true">4.2.</strong> Section 3.1</a></li><li class="chapter-item expanded "><a href="../../ch03/3.3/3.3.html"><strong aria-hidden="true">4.3.</strong> Section 3.3</a></li><li class="chapter-item expanded "><a href="../../ch03/3.4/3.4.html" class="active"><strong aria-hidden="true">4.4.</strong> Section 3.4</a></li><li class="chapter-item expanded "><a href="../../ch03/3.5/3.5.html"><strong aria-hidden="true">4.5.</strong> Section 3.5</a></li><li class="chapter-item expanded "><a href="../../ch03/3.6/3.6.html"><strong aria-hidden="true">4.6.</strong> Section 3.6</a></li><li class="chapter-item expanded "><a href="../../ch03/3.7/3.7.html"><strong aria-hidden="true">4.7.</strong> Section 3.7</a></li><li class="chapter-item expanded "><a href="../../ch03/3.8/3.8.html"><strong aria-hidden="true">4.8.</strong> Section 3.8</a></li><li class="chapter-item expanded "><a href="../../ch03/3.9/3.9.html"><strong aria-hidden="true">4.9.</strong> Section 3.9</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch04/ch04.html"><strong aria-hidden="true">5.</strong> Chapter 4</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch04/key-point/key-point.html"><strong aria-hidden="true">5.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch04/4.2/4.2.html"><strong aria-hidden="true">5.2.</strong> Section 4.2</a></li><li class="chapter-item expanded "><a href="../../ch04/4.3/4.3.html"><strong aria-hidden="true">5.3.</strong> Section 4.3</a></li><li class="chapter-item expanded "><a href="../../ch04/4.4/4.4.html"><strong aria-hidden="true">5.4.</strong> Section 4.4</a></li><li class="chapter-item expanded "><a href="../../ch04/4.5/4.5.html"><strong aria-hidden="true">5.5.</strong> Section 4.5</a></li><li class="chapter-item expanded "><a href="../../ch04/4.6/4.6.html"><strong aria-hidden="true">5.6.</strong> Section 4.6</a></li><li class="chapter-item expanded "><a href="../../ch04/4.7/4.7.html"><strong aria-hidden="true">5.7.</strong> Section 4.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch05/ch05.html"><strong aria-hidden="true">6.</strong> Chapter 5</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch05/5.1/5.1.html"><strong aria-hidden="true">6.1.</strong> Section 5.1</a></li><li class="chapter-item expanded "><a href="../../ch05/5.2/5.2.html"><strong aria-hidden="true">6.2.</strong> Section 5.2</a></li><li class="chapter-item expanded "><a href="../../ch05/5.3/5.3.html"><strong aria-hidden="true">6.3.</strong> Section 5.3</a></li><li class="chapter-item expanded "><a href="../../ch05/5.4/5.4.html"><strong aria-hidden="true">6.4.</strong> Section 5.4</a></li><li class="chapter-item expanded "><a href="../../ch05/5.5/5.5.html"><strong aria-hidden="true">6.5.</strong> Section 5.5</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch06/ch06.html"><strong aria-hidden="true">7.</strong> Chapter 6</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch06/6.1/6.1.html"><strong aria-hidden="true">7.1.</strong> Section 6.1</a></li><li class="chapter-item expanded "><a href="../../ch06/6.2/6.2.html"><strong aria-hidden="true">7.2.</strong> Section 6.2</a></li><li class="chapter-item expanded "><a href="../../ch06/6.3/6.3.html"><strong aria-hidden="true">7.3.</strong> Section 6.3</a></li><li class="chapter-item expanded "><a href="../../ch06/6.4/6.4.html"><strong aria-hidden="true">7.4.</strong> Section 6.4</a></li><li class="chapter-item expanded "><a href="../../ch06/6.5/6.5.html"><strong aria-hidden="true">7.5.</strong> Section 6.5</a></li><li class="chapter-item expanded "><a href="../../ch06/6.6/6.6.html"><strong aria-hidden="true">7.6.</strong> Section 6.6</a></li><li class="chapter-item expanded "><a href="../../ch06/6.7/6.7.html"><strong aria-hidden="true">7.7.</strong> Section 6.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch07/ch07.html"><strong aria-hidden="true">8.</strong> Chapter 7</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch07/7.2/7.2.html"><strong aria-hidden="true">8.1.</strong> Section 7.2</a></li><li class="chapter-item expanded "><a href="../../ch07/7.3/7.3.html"><strong aria-hidden="true">8.2.</strong> Section 7.3</a></li><li class="chapter-item expanded "><a href="../../ch07/7.3/7.4.html"><strong aria-hidden="true">8.3.</strong> Section 7.4</a></li><li class="chapter-item expanded "><a href="../../ch07/7.5/7.5.html"><strong aria-hidden="true">8.4.</strong> Section 7.5</a></li><li class="chapter-item expanded "><a href="../../ch07/7.6/7.6.html"><strong aria-hidden="true">8.5.</strong> Section 7.6</a></li><li class="chapter-item expanded "><a href="../../ch07/7.7/7.7.html"><strong aria-hidden="true">8.6.</strong> Section 7.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch08/ch08.html"><strong aria-hidden="true">9.</strong> Chapter 8</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch08/8.2/8.2.html"><strong aria-hidden="true">9.1.</strong> Section 8.2</a></li><li class="chapter-item expanded "><a href="../../ch08/8.3/8.3.html"><strong aria-hidden="true">9.2.</strong> Section 8.3</a></li><li class="chapter-item expanded "><a href="../../ch08/8.4/8.4.html"><strong aria-hidden="true">9.3.</strong> Section 8.4</a></li><li class="chapter-item expanded "><a href="../../ch08/8.5/8.5.html"><strong aria-hidden="true">9.4.</strong> Section 8.5</a></li></ol></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">PurpleDragonBookAnswer</h1>

                    <div class="right-buttons">
                        <a href="../../print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="34-节的练习"><a class="header" href="#34-节的练习">3.4 节的练习</a></h1>
<h3 id="341"><a class="header" href="#341">3.4.1</a></h3>
<p>给出识别练习 3.3.2 中各个正则表达式所描述的语言状态转换图。</p>
<h4 id="解答"><a class="header" href="#解答">解答</a></h4>
<p>解答步骤：NFA -&gt; DFA -&gt; 最少状态的 DFA（状态转换图）</p>
<ol>
<li>a(a|b)*a</li>
</ol>
<p>NFA:</p>
<p><img src="./assets/3.4.1-1-nfa.gif" alt="3 4 1-1-nfa" /></p>
<p>DFA:
转换表：</p>
<table>
<thead>
<tr>
<th>NFA</th>
<th>DFA</th>
<th>a</th>
<th>b</th>
</tr>
</thead>
<tbody>
<tr>
<td>{0}</td>
<td>A</td>
<td>B</td>
<td></td>
</tr>
<tr>
<td>{1,2,3,5,8}</td>
<td>B</td>
<td>C</td>
<td>D</td>
</tr>
<tr>
<td>{2,3,4,5,7,8,<b>9</b>}</td>
<td><b>C</b></td>
<td>C</td>
<td>D</td>
</tr>
<tr>
<td>{2,3,5,6,7,8}</td>
<td>D</td>
<td>C</td>
<td>D</td>
</tr>
</tbody>
</table>
<p>转移图：
<img src="./assets/3.4.1-1-dfa.gif" alt="3 4 1-1-dfa" /></p>
<p>​    最少状态的 DFA(状态转换图):</p>
<blockquote>
<p>合并不可区分的状态 B 和 D</p>
</blockquote>
<p><img src="./assets/3.4.1-1.gif" alt="3 4 1-1" /></p>
<ol start="2">
<li>
<p>((ε|a)b*)*</p>
<p>直接给出最小化DFA：</p>
<p><img src="./assets/3.4.1-2.gif" alt="3 4 1-2" /></p>
</li>
<li>
<p>(a|b)*a(a|b)(a|b)</p>
</li>
</ol>
<p>NFA:</p>
<p><img src="./assets/3.4.1-3-nfa.gif" alt="3 4 1-3-nfa" /></p>
<p>DFA:
转换表：</p>
<table>
<thead>
<tr>
<th>NFA</th>
<th>DFA</th>
<th>a</th>
<th>b</th>
</tr>
</thead>
<tbody>
<tr>
<td>{0,1,2,4,7}</td>
<td>A</td>
<td>B</td>
<td>C</td>
</tr>
<tr>
<td>{1,2,3,4,6,7,8,9,11}</td>
<td>B</td>
<td>D</td>
<td>E</td>
</tr>
<tr>
<td>{1,2,4,5,6,7}</td>
<td>C</td>
<td>B</td>
<td>C</td>
</tr>
<tr>
<td>{1,2,3,4,6,7,8,9,10,11,13,14,16}</td>
<td>D</td>
<td><b>F</b></td>
<td><b>G</b></td>
</tr>
<tr>
<td>{1,2,4,5,6,7,12,13,14,16}</td>
<td>E</td>
<td><b>H</b></td>
<td><b>I</b></td>
</tr>
<tr>
<td>{1,2,3,4,6,7,8,9,10,11,13,14,15,16,<b>18</b>}</td>
<td><b>F</b></td>
<td><b>F</b></td>
<td><b>G</b></td>
</tr>
<tr>
<td>{1,2,4,5,6,7,12,13,14,16,17,<b>18</b>}</td>
<td><b>G</b></td>
<td><b>H</b></td>
<td><b>I</b></td>
</tr>
<tr>
<td>{1,2,3,4,6,7,8,9,11,15,<b>18</b>}</td>
<td><b>H</b></td>
<td>D</td>
<td>E</td>
</tr>
<tr>
<td>{1,2,4,5,6,7,17,<b>18</b>}</td>
<td><b>I</b></td>
<td>B</td>
<td>C</td>
</tr>
</tbody>
</table>
<p>​	最少状态的 DFA(状态转换图):</p>
<blockquote>
<p>合并不可区分的状态 A 和 C</p>
</blockquote>
<p><img src="./assets/3.4.1-3.gif" alt="3 4 1-3" /></p>
<p>​<br />
4. a*ba*ba*ba*</p>
<pre><code>直接给出最小化DFA：

![3 4 1-4](./assets/3.4.1-4.gif)
</code></pre>
<h3 id="342"><a class="header" href="#342">3.4.2</a></h3>
<p>给出识别练习 3.3.5 中各个正则表达式所描述语言的状态转换图。</p>
<h3 id="343"><a class="header" href="#343">3.4.3</a></h3>
<p>构造下列串的失效函数。</p>
<ol>
<li>abababaab</li>
<li>aaaaaa</li>
<li>abbaabb</li>
</ol>
<h4 id="解答-1"><a class="header" href="#解答-1">解答</a></h4>
<p>代码如下：</p>
<pre><code class="language-javascript">module.exports = failureFunction

function failureFunction(str) {
    var failure = [0]
    var j = 0
    for (var i = 1; i &lt; str.length; i++) {
        while(j &gt; 0 &amp;&amp; str[j] != str[i]) {
            j = failure[j-1]
        }
        if(str[j] == str[i]){
            j++
        }
        failure[i] = j
    }
    return failure
}

</code></pre>
<ol>
<li>[ 0, 0, 1, 2, 3, 4, 5, 1, 2 ]</li>
<li>[ 0, 1, 2, 3, 4, 5 ]</li>
<li>[ 0, 0, 0, 1, 1, 2, 3 ]</li>
</ol>
<h3 id="344-"><a class="header" href="#344-">3.4.4 ！</a></h3>
<p>对 s 进行归纳，证明图 3-19 的算法正确地计算出了失效函数。</p>
<p><strong>图 3-19：计算关键字 b_1b_2…b_n 的失效函数</strong></p>
<pre><code>01  t = 0;
02  f(1) = 0;
03  for (s = 1; s &lt; n; s ++){
04      while( t &gt; 0 &amp;&amp; b_s+1 != b_t+1) t = f(t);
05      if(b_s+1 == b_t+1){
06          t = t + 1;
07          f(s + 1) = t;
08      }else{
09          f(s + 1) = 0;
10      }
11  }
</code></pre>
<h4 id="证明"><a class="header" href="#证明">证明</a></h4>
<ol>
<li>已知 f(1) = 0</li>
<li>在第 1 次 for 循环时，计算 f(2) 的值，当第5行代码 b_2 == b_1 成立时，代码进入到第7行得出 f(2) = 1，不成立时，则代码进入第9行得出 f(2) = 0。显然，这次循环正确的计算出了 f(2) 。</li>
<li>假设在第 i-1 次进入循环时，也正确的计算出了 f(i)，也有 f(i) = t (无论 t 是大于 0 还是等于 0)</li>
<li>那么在第 1 次进入循环时，分两种情况进行考虑：
<ol>
<li>
<p>t == 0</p>
<p>这种情况比较简单，直接从第 5 行开始，当 b_i+1 == b_1 时，f(i+1) = 1，否则 f(i+1) = 0</p>
</li>
<li>
<p>t &gt; 0
while 循环会不断缩小 t 值，试图找出最大可能的使得 b_i+1 == b_t+1 成立的 t 值，如果找到了，则进入第 5 行执行，得到 f(i+1) = t+1；或者直到 t == 0 时也没有找到，则跳出循环，这时进入第 5 行执行，过程类似于前一种情况。</p>
</li>
</ol>
</li>
</ol>
<h3 id="345-"><a class="header" href="#345-">3.4.5 ！！</a></h3>
<p>说明图 3-19 中的第 4 行的复制语句 t = f(t) 最多被执行 n 次。进而说明整个算法的时间复杂度是 O(n)，其中 n 是关键字长度。</p>
<h4 id="解答-2"><a class="header" href="#解答-2">解答</a></h4>
<p>详见 matrix 的博文 <a href="http://www.matrix67.com/blog/archives/115">KMP算法详解</a>。</p>
<h3 id="346"><a class="header" href="#346">3.4.6</a></h3>
<p>应用 KMP 算法判断关键字 ababaa 是否为下面字符串的子串：</p>
<ol>
<li>abababaab</li>
<li>abababbaa</li>
</ol>
<h4 id="解答-3"><a class="header" href="#解答-3">解答</a></h4>
<p>代码如下：</p>
<pre><code class="language-javascript">var failureFunction = require('./failure-function')

module.exports = kmp

function kmp(str, search) {
    var failure = failureFunction(search)
    var s = 0
    for (var i = 0; i &lt; str.length; i++) {
        while (s &gt; 0 &amp;&amp; str[i] != search[s]) {
            s = failure[s-1]
        }
        if(str[i] == search[s]){
            s = s + 1
        }
        if(s == search.length){
            return true
        }
    }
    return false
}
</code></pre>
<p>结果：</p>
<ol>
<li>true</li>
<li>false</li>
</ol>
<h3 id="347-"><a class="header" href="#347-">3.4.7 ！！</a></h3>
<p>说明图 3-20 中的算法可以正确的表示输入关键字是否为一个给定字符串的子串。</p>
<p><strong>图 3-20：KMP 算法在 O(m + n) 的时间内检测字符串a_1a_3...a_n 中是否包含单个关键字 b1b2...bn</strong></p>
<pre><code>s = 0;
for(i = 1; i &lt;= m; i ++){
    while(s &gt; 0 &amp;&amp; a_i != b_s+1) s = f(s);
    if(a_i == b_s+1) s = s + 1;
    if(s == n) return &quot;yes&quot;;
}
return &quot;no&quot;;
</code></pre>
<h3 id="348"><a class="header" href="#348">3.4.8</a></h3>
<p>假设已经计算得到函数 f 且他的值存储在一个以 s 为下标的数字中，说明图 3-20 中算法的时间复杂度为 O(m + n)。</p>
<h4 id="解答-4"><a class="header" href="#解答-4">解答</a></h4>
<p>详见 matrix 的博文 <a href="http://www.matrix67.com/blog/archives/115">KMP算法详解</a>。</p>
<h3 id="349"><a class="header" href="#349">3.4.9</a></h3>
<p>Fibonacci 字符串的定义如下：</p>
<ol>
<li>s1 = b</li>
<li>s2 = a</li>
<li>当 k &gt; 2 时， s<sub>k</sub> = s<sub>k-1</sub> s<sub>k-2</sub></li>
</ol>
<p>例如：s<sub>3</sub> = ab, s<sub>4</sub> = aba, s<sub>5</sub> = abaab</p>
<ol>
<li>s<sub>n</sub> 的长度是多少？</li>
<li>构造 s<sub>6</sub> 的失效函数。</li>
<li>构造 s<sub>7</sub> 的失效函数。</li>
<li>！！ 说明任何 s<sub>n</sub> 的失效函数都可以被表示为：f(1) = f(2) = 0，且对于 2 &lt; j &lt;= |s<sub>n</sub>|, f(j) = j - |s<sub>k-1</sub>|，其中 k 是使得 |s<sub>k</sub>| &lt;= j + 1 的最大整数。</li>
<li>！！ 在 KMP 算法中，当我们试图确定关键字 s<sub>k</sub> 是否出现在字符串 s<sub>k+1</sub> 中，最多会连续多少次调用失效函数？</li>
</ol>
<h4 id="解答-5"><a class="header" href="#解答-5">解答</a></h4>
<ol>
<li>
<p>见 <a href="http://zh.wikipedia.org/wiki/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97">维基百科</a></p>
</li>
<li>
<p>s<sub>6</sub> = abaababa</p>
<p>failure = [ 0, 0, 1, 1, 2, 3, 2, 3 ]</p>
</li>
<li>
<p>s<sub>7</sub> = abaababaabaab</p>
<p>failure = [ 0, 0, 1, 1, 2, 3, 2, 3, 4, 5, 6, 4, 5 ]</p>
</li>
</ol>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="../../ch03/3.3/3.3.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="../../ch03/3.5/3.5.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="../../ch03/3.3/3.3.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="../../ch03/3.5/3.5.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="../../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="../../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
